class LRUCache {

    public class Node {
        public int key;
        public int val;
        public Node prev;
        public Node next;

        public Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node head;
    public Node tail;
    int n;
    Map<Integer,Node> map;

    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.val;
        }

        return 0;
    }

    public void put(int key, int value) {
        Node node = null;
        if(map.containsKey(key)) {
            //存在就覆盖
            node = map.get(key);
            node.val = value;
        } else {
            //不存在
            if(n == map.size()) {
                Node del = tail.prev;
                delete(del);
                map.remove(del.val);
            }
            node = new Node(key,value);
            map.put(key,node);
        }
        refresh(node);
    }

    private void refresh(Node node) {
        //删除
        delete(node);
        //放到头部
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
    }

    private void delete(Node node) {
        if(node.next!=null) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */